A votre avis, combien de couleurs nécessite le coloriage de toute carte de géographie, même la plus compliquée qui puisse exister ? Eh bien, messieurs les géographes, 4 couleurs vous suffisent amplement ! Ne nous demandez pas de vous le démontrer, il parait qu’on n’y est parvenu qu’avec l’aide de puissants ordinateurs... (Appel et Hacken en 1976). En revanche, si vous n’êtes pas convaincu que cinq couleurs vous permettent de colorier une carte, nous pouvons vous le prouver.

• Une relation utile.

Considérons la carte d’un continent (entouré par la mer) ; on introduit les notations suivantes :

n : nombre de pays de ce continent. On suppose qu’ils sont "d’un seul tenant" (interdit à un pays d’avoir une colonie dans le même continent). Par contre, rien n’interdit qu’un pays soit inclus dans un autre (cf. le Portugal dans l’Espagne).

p : nombre de points frontière dans cette carte. Soyons plus précis : on entend par point frontière le point de rencontre de plusieurs frontières (au moins trois) à l’intérieur des terres (les points d’arrivée des frontières à la mer n’entrent donc pas en compte).

Un point frontière sera dit de degré d si d frontières y convergent.

q : nombre de frontières terrestres dans ce continent, c’est à dire le nombre de lignes séparant deux pays, dont les extrémités sont des points frontière ou la mer.
 

Ainsi dans la carte ci-dessous, le nombre n de pays est 12, le nombre p de points frontière 6, le nombre q de frontières est 17.

Nous allons démontrer que ces trois éléments d’une carte sont liés par la relation :

• Une démonstration par récurrence.
 

Nous avons procédé par récurrence triple sur q ; soit P(q) la propriété :

" Quelles que soient les valeurs de n et de p, q = n + p - 1 ".
 

Première étape : vérification de P(q) pour les trois premières valeurs de q.
 

• Pour q = 0 (pas de frontière), n = 1 (il ne peut y avoir qu’un seul pays) et  p = 0. On a bien .

P(0) est vraie.

• Pour q = 1 (une seule frontière), n= 2 (il ne peut y avoir que deux pays) et  p = 0. On a bien encore .

P(1) est vraie.
 

• Pour q = 2 (deux frontières), p = 0 encore, car un point frontière nécessite au moins trois frontières, et donc n = 3 (il ne peut y avoir que trois pays dont deux ne se touchent pas). On a encore q = n + p - 1.

P(2) est vraie.
 

Deuxième étape : on suppose P(q) vraie, P(q - 1) vraie et P(q - 2) vraie (hypothèse de récurrence).

Montrons que P(q + 1) est vraie.

Considérons donc une carte ayant q + 1 frontières, n pays et p points frontière ;

Pour nous ramener au cas de l’hypothèse de récurrence, nous allons carrément supprimer une frontière F de cette carte. Après cette opération, deux pays n’en font plus qu’un seul, et nous avons donc n - 1 pays.
 

Pour les points frontière et les frontières, trois cas peuvent se produire, suivant les degrés des points frontière délimitant F.
 

Si ces points frontière sont tous deux de degré  4, le nombre de frontières de la nouvelle configuration est q, le nombre de points frontière est p, le nombres de pays n - 1.

En appliquant l’hypothèse de récurrence, on a : q = (n - 1) + p -1 et donc q + 1 = n + p -1.
 

Si l’un de ces points frontière est de degré 3, et l’autre de degré  4, le point frontière de degré 3 disparaît dans la nouvelle configuration, entraînant la réunion de deux frontières en une seule. On se retrouve avec (n -1 ) pays, (p - 1) points frontière et (q - 1) frontières.

En appliquant l’hypothèse de récurrence, on a : q - 1 = (n - 1) + (p - 1) -1 et donc q + 1 = n + p -1.
 

Nous laissons au lecteur le plaisir de constater que tout marche bien également lorsque les deux points frontière sont de degré trois, lorsque l’une des extrémités de F est à la mer, et enfin lorsque les deux y sont.

• Une propriété générale.

Maintenant, partons de trois constatations toutes simples découlant des définitions précédentes :

C1 . A une même frontière, correspondent exactement 2 pays.
 

C2. Une même frontière est délimitée par au plus 2 points frontière.
 

C3. En un même point frontière convergent au moins 3 frontières.
 

Schématisons par des patates l’ensemble des points frontières noté A et l’ensemble des frontières noté B et relions par un segment l'élément de A à un élément de B si la frontière est limitée par les points frontières correspondants. Soient card(A) = p et  card(B) = q  et l le nombre de segments ;

alors les propriétés ci-dessus impliquent :
 
 

On en tire 3p2q. Or , d’où

Nous allons en déduire, en raisonnant par l’absurde, une propriété générale :
 

Dans toute carte de géographie il existe toujours un pays qui ne possède pas plus de 5 pays voisins.
 

Supposons en effet que dans une certaine carte de géographie, tous les pays ont au moins 6 pays voisins, donc 6 frontières. On aurait alors la relation :

(une même frontière étant commune à deux pays)

par suite, en utilisant la propriété P(q), on obtiendrait :

soit 2n + 1  p , ce qui est en contradiction avec la relation encadrée ci-dessus.

Conclusion partielle : dans toute carte de géographie il existe toujours au moins un pays qui ne possède pas plus de 5 pays voisins.
 
 

Le problème est désormais de savoir si l’on peut abaisser le nombre 5 : en d’autres termes, existe - t - il une carte dont tous les pays auraient au moins 5 voisins chacun ?
 

Or nous avons trouvé ce contre exemple, et nous vous le présentons non sans une certaine fierté.

Nous avons donc montré que quelle que soit la carte de géographie considérée, il existe toujours un pays n’ayant pas plus de cinq frontières communes, et que, de plus ce nombre cinq, ne peut pas être abaissé.

• Le théorème

Démontrons enfin le théorème lui-même, à savoir qu’avec un maximum de cinq couleurs, on peut colorier n’importe quelle carte.

Il suffit pour cela de raisonner par récurrence. Vous commencez à avoir l’habitude !

Il est bien évident que l’on peut colorier UN pays avec un choix de cinq couleurs !

Prenons pour hypothèse de récurrence le fait que l’on puisse, avec cinq couleurs colorier une carte possédant N pays (la récurrence porte sur le nombre N).

Considérons une carte possédant N + 1 pays. D’après ce que l’on a vu précédemment, on peut dire que dans cette carte il existe au moins un pays P n’ayant pas plus de cinq frontières.

On supprime alors momentanément une frontière de ce pays. La carte contient désormais N pays. D’après l’hypothèse de récurrence, cette carte est coloriable avec un maximum de cinq couleurs différentes.

Après avoir colorié cette carte, on reconstitue la frontière enlevée. Seul le pays P que l’on a isolé reste incolore. Il n’a de plus qu’un maximum de 5 pays voisins.

Deux cas se présentent :

- Parmi les pays voisins, au moins deux pays ont la même couleur, alors il reste une couleur disponible pour colorier P.

- P possède 5 voisins dont toutes les couleurs sont différentes :

Considérons les pays A et C coloriés respectivement en a et en c :
 

- S’il n’existe pas de suite de pays coloriés en a ou en c se touchant par au moins l’une de leurs frontières, permettant de joindre A et C (un anneau de Kempe), on peut colorier A en c, et inverser les couleurs a et c de proche en proche. On se ramène au cas précédent et P peut alors être colorié en a.
 

- S’il existe une telle suite, les pays B et D coloriés respectivement en b et en d ne peuvent être les extrémités d’une suite de pays de couleurs b et d (pour des raisons évidentes de connexité). En faisant le raisonnement précédent, on peut donc colorier B en d, et donc P en b.
 

On peut donc colorier une carte possédant N + 1 pays avec un maximum de cinq couleurs. La propriété est vraie à l’ordre N + 1, ce qui achève la récurrence.
 

Conclusion : on peut donc colorier toute carte de géographie d’un continent avec un maximum de cinq couleurs différentes.
 

Et remarquons que la méthode que nous avons utilisée constitue un algorithme de coloration.
 

• Des généralisations

On aimerait bien pouvoir démontrer le théorème des quatre couleurs par la même méthode des échanges de couleur. C’est ce qu’avait cru pouvoir faire Kempe au 19ème siècle. Pendant dix ans, personne n’a remarqué son erreur !

Remarquons que si quelle que soit la carte de géographie considérée, il existait toujours un pays n’ayant pas plus de quatre frontières communes, on démontrerait

le théorème des quatre couleurs par cette méthode...

Bien sur, cette propriété est fausse, mais vu le mal que nous avons eu à trouver la carte où tous les pays ont au moins cinq voisins, ces cartes ne doivent pas courir les rues ...

Nous énoncerons donc un :

Théorème faible des quatre couleurs : si dans une carte l’un des pays n’a pas plus de quatre voisins, et qu’en supprimant l’une des frontières de ce pays (s’il en a au moins une), on obtient une carte ayant la même propriété, alors cette carte est coloriable à l’aide de quatre couleurs.
 

Vous constaterez cependant en consultant n’importe quel atlas que les pays ont très souvent cinq à six voisins chacun (et remarquer par la même occasion que les géographes utilisent habituellement nettement plus de quatre couleurs !). Il faut plutôt chercher les pays ayant un accès à la mer...

Nous nous sommes aussi posé le problème de la généralisation à l’espace. Les choses sont alors beaucoup plus simples : on peut en effet trouver n objets (même des polyèdres) tels que chacun de ces objets touche les n - 1 autres, et sur une surface non nulle. Une figure suffit pour décrire le contre-exemple que nous avons trouvé :

Il n'y a donc pas de théorème de limitation de couleur dans l'espace : n objets qui se touchent mutuellement nécessitent n couleurs pour être coloriés.
 

Une autre piste enfin, que nous n’avons pas explorée, est de considérer des pays qui peuvent être morcelés. Nous renvoyons le lecteur à un article de Ian Stewart : Visions géométriques, le coloriage des empire (P. 149), Belin, 1994.
 

RETOUR